package Tree;

import java.util.ArrayList;
import java.util.List;

/*
*给定一个二叉树的根节点 root ，返回它的 中序 遍历。
*
*
* */
public class item94 {
}

 // Definition for a binary tree node.
 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution {
    public static List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<>();
        inorder(root,res);
        return res;
    }

    private  static void inorder(TreeNode root, List<Integer> res) {
        if(root!=null)
        {   System.out.println("第一次到"+root.val);
            inorder(root.left,res);
            System.out.println("第二次到"+root.val);
            res.add(root.val);

            inorder(root.right, res);
            System.out.println("第三次到"+root.val);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode  node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(5);
        TreeNode node5 = new TreeNode(6);
        TreeNode node6 = new TreeNode(7);
        root.left= node1;
        root.right  = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        inorderTraversal(root);

    }
}